package cn.bellychang.skiplist.wangwenjun;

import java.util.Objects;
import java.util.Random;

/**
 * SkipList must be an ordered list
 * skip list's features:
 * 1. a random data structure
 * 2. the lowest layer contains all the elements in the skip list
 * 3. typical space-for-time algorithm
 *
 * @author: bellychang
 * @date: 2020/2/5
 */
public class SkipList<E extends Comparable> {

    /**
     * define node type's constant value
     */
    private final static byte HEAD_TYPE = -1;
    private final static byte TAIL_TYPE = 1;
    private final static byte DATA_TYPE = 0;
    public static final double RANDOM_FACTOR = 0.8d;

    private static class Node<E extends Comparable> {
        private E value;
        private Node<E> left, right, up, down;
        private byte type;

        public Node(E value, byte type) {
            this.value = value;
            this.type = type;
        }

        public Node(E value) {
            this.value = value;
            this.type = DATA_TYPE;
        }

        public E getValue() {
            return value;
        }

/*        @Override
        public String toString() {
            return value.toString();
        }*/
    }

    private Node head;
    private Node tail;
    private int size;
    private int height;
    private Random random;
    private int maxHeight;

    public SkipList(int maxHeight) {
        this.head = new Node(null, HEAD_TYPE);
        this.tail = new Node(null, TAIL_TYPE);
        head.right = tail;
        tail.left = head;
        this.maxHeight = maxHeight;
        this.random = new Random(System.currentTimeMillis());
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private Node<E> find(E element) {
        Node temp = head;
        for (; ; ) {
            // find the temp <= element < temp.right
            while ((temp.right.type != TAIL_TYPE && temp.right.value.compareTo(element) <= 0)) {
                temp = temp.right;
            }
            if (Objects.nonNull(temp.down)) {
                temp = temp.down;
            } else {
                break;
            }
        }
        return temp;
    }

    public boolean contains(E element) {
        Node<E> lessNode = this.find(element);
        return lessNode.getValue().compareTo(element) == 0;
    }

    public void add(E element) {
        Node<E> lessNode = this.find(element);
        Node newNode = new Node(element);

        newNode.right = lessNode.right;
        newNode.left = lessNode;
        // pay attention to this sequence, cannot be reversed
        lessNode.right.left = newNode;
        lessNode.right = newNode;

        // test if need promote this element to a upper layer
        int currentLevel = 0;
        while (random.nextDouble() < RANDOM_FACTOR && height <= (maxHeight - 2)) {

            // test if exceed the getHeight of skip list
            if (currentLevel >= height) {
                addEmptyLevel();
            }
            // find the position in the upper layer
            // scan node who has upper node from lessNode in the left direction
            while ((lessNode != null) && lessNode.up == null) {
                lessNode = lessNode.left;
            }
            // when satisfy lessNode.up!=null, code could run here
            // lessNode == null never could happen, because of head !=null and it will have an empty upper layer
            lessNode = lessNode.up;

            Node<E> upperNewNode = new Node(element);
            // Three-way connection should be established
            upperNewNode.down = newNode;
            newNode.up = upperNewNode;

            upperNewNode.left = lessNode;
            upperNewNode.right = lessNode.right;

            // cannot reverse the sequence
            lessNode.right.left = upperNewNode;
            lessNode.right = upperNewNode;

            // perhaps after this newNode promotion to upper layer,
            // this upperNewNode still need to promote to the next upper layer
            newNode = upperNewNode;

            currentLevel++;
        }
        size++;
    }

    private void addEmptyLevel() {

        height++;

        Node dummyHead = new Node(null, HEAD_TYPE);
        Node dummyTail = new Node(null, TAIL_TYPE);

        dummyHead.right = dummyTail;
        dummyHead.down = head;
        head.up = dummyHead;

        dummyTail.left = dummyHead;
        dummyTail.down = tail;
        tail.up = dummyTail;

        // head and tail move upwards
        head = dummyHead;
        tail = dummyTail;
    }


    public void showSkipList() {
        Node temp = head;
        while (temp.up != null) {
            temp = temp.up;
        }
        System.out.print(temp);
        System.out.print(":head\n");
        for (int i = height; i >= 0; i--) {
            System.out.printf("Total getHeight: [%d], current getHeight: [%d]\n", height + 1, i + 1);
            if (Objects.nonNull(temp)) {
                Node node = temp.right;
                while (node.type == DATA_TYPE) {
                    System.out.print("  ");
                    System.out.print(node);
                    System.out.print(":data");
                    System.out.printf("->%d", node.value);
                    node = node.right;
                }
                System.out.printf("\n");
                temp = temp.down;
                if (Objects.nonNull(temp)) {
                    System.out.print(temp);
                    System.out.print(":head\n");
                }
            }
        }
        System.out.println("===========================");
    }

    public void dumpSkipList() {
        Node temp = head;
        while (temp.up != null) {
            temp = temp.up;
        }
        for (int i = height; i >= 0; i--) {
//            System.out.printf("Total getHeight: [%d], current getHeight: [%d]\getSize", getHeight + 1, i + 1);
            if (Objects.nonNull(temp)) {
                Node node = temp.right;
                while (node.type == DATA_TYPE) {
                    System.out.printf("->%d", node.value);
                    node = node.right;
                }
                System.out.printf("\n");
                temp = temp.down;
            }
        }
        System.out.println("===========================");
    }


}
